googologywikiaorg-20200223-history
User blog:Deedlit11/So what the hell is a diagonalizer?
A while ago FB100Z asked what a diagonalizer was, so I figured I would write a post explaining them a bit. The original "diagonalizer" is the cardinal \(\Omega\) in Bachmann's original notation, and, while in the definition it is really an ordinal, it can be thought of as a formal symbol telling us what function to take fixed points of. Some examples: \(\theta (\Omega, \alpha)\) is the \(\alpha\)th fixed point of \(f(\beta) = \theta(\beta, 0)\). \(\theta (\Omega 2, \alpha)\) is the \(\alpha\)th fixed point of \(f(\beta) = \theta (\Omega + \beta, 0)\). \(\theta (\Omega^2, \alpha)\) is the \(\alpha\)th fixed point of \(f(\beta) = \theta (\Omega \beta, 0)\). \(\theta (\Omega^\Omega, \alpha)\) is the \(\alpha\)th fixed point of \(f(\beta) = \theta (\Omega^\beta, 0)\). \(\theta (\Omega^{\Omega^\Omega} + \Omega^{\Omega^5 + \Omega^3 2 + \Omega^2 6}, \alpha)\) is the \(\alpha\)th fixed point of \(f(\beta) = \theta(\Omega^{\Omega^\Omega} + \Omega^{\Omega^5 + \Omega^3 2 + \Omega^2 5 + \Omega \beta}, 0)\). Hopefully you can see the general pattern. Basically to compute \(\theta(\gamma, \alpha)\), you take the final \(\Omega\) appearing in the expression for \(\gamma\) and replace it with \(\beta\), and this gives you the function of \(\beta\) that you take the \(\alpha\)th fixed point of. Note that you may need to expand the expression for \(\gamma\) to see the final \(\Omega\). For example, if \(\gamma = \Omega^{\Omega+1}\), we need to expand it as \(\gamma = \Omega^\Omega \Omega\), so therefore we take fixed points of \(f(\beta) = \theta (\Omega^\Omega \beta, 0)\). Also, \(\gamma\) may end in an \(\omega\) or a \(1\) rather than an \(\Omega\) (meaning its cofinality is \(\omega\) or \(1\) rather than \(\Omega\)). In that case, the rules are different. For example: \(\theta (\Omega \omega, \alpha)\) is the \(\alpha\)th ordinal that is a fixed point of \(f(\beta) = \theta(\Omega n,\beta) \) for all \(n < \omega\). \(\theta (\Omega\omega + 1, \alpha)\) is the \(\alpha\)th fixed point of \(f(\beta) = \theta (\Omega \omega, \beta)\). The way to make this notion formal is by way of fundamental sequences. For an ordinal of cofinality \(\Omega\), its fundamental sequence will be of length \(\Omega\). We can define the fundamental sequences for ordinals less than \(\Gamma_{\Omega+1}\) as follows: \(\Omega \alpha = \alpha\) If \(\gamma = \gamma_1 + \gamma_2 + \ldots + \gamma_n\) where the \(\gamma_i\) are principal ordinals (powers of \(\omega\)) and the cofinality of \(\gamma_n\) is \(\Omega\), then \(\gamma\alpha = \gamma_1 + \gamma_2 + \ldots + \gamma_{n-1} + (\gamma_n \alpha)\) If \(\gamma\) is of cofinality \(\Omega\), then \(\varphi (\beta, \gamma) \alpha = \varphi (\beta, \gamma \alpha)\) If \(\beta\) is of cofinality \(\Omega\), then \(\varphi (\beta, 0) \alpha = \varphi (\beta \alpha, 0)\) If \(\beta\) is of cofinality \(\Omega\), then \(\varphi (\beta, \gamma+1) \alpha = \varphi (\beta \alpha, \varphi(\beta, \gamma) + 1)\) We can then define \(\theta(\gamma, \alpha)\) for \(\gamma\) of cofinality \(\Omega\) as the \(\alpha\)th fixed point of \(f(\beta) = \theta (\gamma\beta, 0)\). So, \(\Omega\) being the diagonalizer for the \(\theta\) function means that, when the cofinality of \(\gamma\) is less than \(\Omega\), we define \(\theta(\gamma, \alpha)\) using the traditional rules for the function, and if the cofinality of \(\gamma\) is \(\Omega\), we define \(\theta (\gamma, \alpha)\) as the \(\alpha\)the fixed point of a certain fixed point using the fundamental sequence for \(\gamma\). We can have a notation with many diagonalizers. Take the notation for \(\vartheta (\Omega_{\Omega_{\Omega \ldots}})\) described in my blog post Ordinal Notations III. \(\Omega_\alpha\) is a diagonalizer for \(\vartheta_\beta\) precisely when \(\text{cof}(\Omega_\alpha) > \Omega_\beta\). When \(\text{cof}(\Omega_\alpha) = \Omega_{\beta+1})\), we can call \(\Omega_\alpha\) a "natural diagonalizer" for \(\vartheta_\beta\), and the definition works much like above. For example, \(\vartheta_3 (\Omega_4)\) is the first fixed point of the function \(f(\beta) = \vartheta_3 (\beta)\), and if \(\gamma\) has cofinality \(\Omega_4\), then \(\vartheta_3(\gamma)\) is the first fixed point of the funciton \(f(\beta) = \vartheta_3 (\gamma\beta)\). For a non-natural diagonalizer \(\gamma\), we can insert a \(\vartheta_\alpha\) such that \(\gamma\) is a natural diagonalizer for \(\vartheta_\alpha\). So for example \(\vartheta_3 (\Omega_6 3)\) can be rewritten as \(\vartheta_3 (\vartheta_5 (\Omega_6 3)) = \vartheta_3 (\alpha)\), where \(\alpha\) is the first fixed point of \(f(\beta) = \vartheta_5 (\Omega_6 2 + \beta)\). Note that \(\Omega_\omega\) is not the diagonalizer of any function; we simply think of it as the limit of \(\Omega_1, \Omega_2, \ldots\) . So far, we have defined diagonalizers as symbols that indicate where we take fixed points. But when we get to stronger notations, we get a different kind of diagonalizer. The canonical example is \(M\) in the ordinal notation for KPM, described in Ordinal Notations V. For this notation, we have the notion of a hierarchy of weakly inaccessible cardinals; \(I(\alpha)\) is the \(\alpha\)th weakly inaccesible cardinal \(I(1, \alpha)\) is the \(\alpha\)th 1-weakly inaccessible cardinal \(I(2, \alpha)\) is the \(\alpha\)th 2-weakly inaccessible cardinal \(I(1, 0, \alpha)\) is the \(\alpha\)th ordinal \(\beta\) such that \(\beta\) is a \(\beta\)-weakly inaccessible cardinal (which we can call a (1,0)-weakly inaccessible cardinal) and the hierachy continues from there to arbitrarily many variables. The idea behind \(M\) is to define a function \(\chi\) such that \(\chi (M^n \alpha_n + M^{n-1} \alpha_{n-1} + \ldots M \alpha_1 + \alpha_0) = I(\alpha_n, \alpha_{n-1}, \ldots, \alpha_1, \alpha_0) \) so the coefficients of \(M^i\) represent the variables in the inaccessible hierarchy, and we have a way of collapsing the many variable hierarchy to a function of a single variable. But, we can go on to \(\chi(M^\omega), \chi(M^M), \chi(M^{M^M}), \chi(\varepsilon_{M+1}), \chi(\Gamma_{M+1})\), and so on. So instead of being a symbol that indicates fixed points, we can have a diagonalizer whose coefficients represent the variables in a many variable hierarchy. So we have a more general notion than just fixed points. Category:Blog posts